// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class Code08_CompletenessOfBinaryTree {

    // 不提交这个类
    // TreeNode类用于表示二叉树的节点，其中val表示节点的值，left和right分别表示左子节点和右子节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 提交以下的方法
    // 如果测试数据量变大了就修改这个值
    // MAXN用于定义队列的最大容量，这里假设足够容纳二叉树的节点
    public static int MAXN = 101;
    // 定义一个TreeNode类型的数组queue用于层次遍历二叉树时存储节点
    public static TreeNode[] queue = new TreeNode[MAXN];
    // l用于表示队列的头部索引，r用于表示队列的尾部索引
    public static int l, r;

    // 此方法用于判断给定的二叉树h是否为完全二叉树
    public static boolean isCompleteTree(TreeNode h) {
        // 如果传入的二叉树h为null，空树被认为是完全二叉树，直接返回true
        if (h == null) {
            return true;
        }
        // 初始化队列的头部索引l和尾部索引r为0
        l = r = 0;
        // 将根节点h放入队列queue中，同时将尾部索引r加1
        queue[r++] = h;
        // 定义一个布尔变量leaf，用于标记是否已经遇到过左右孩子不双全的节点，初始化为false
        boolean leaf = false;

        // 开始层次遍历二叉树，只要队列头部索引l小于尾部索引r，就继续循环
        while (l < r) {
            // 取出队列头部的节点h
            h = queue[l++];
            // 进行两种不符合完全二叉树的情况判断：
            // 1. 如果当前节点h的左子节点为null而右子节点不为null，这违反了完全二叉树的节点特性，直接返回false
            // 2. 如果已经遇到过leaf为true（即已经遇到过孩子节点不双全的节点），并且当前节点h的左子节点或者右子节点不为null，这也不符合完全二叉树的特性，返回false
            if ((h.left == null && h.right!= null) || (leaf && (h.left!= null || h.right!= null))) {
                return false;
            }
            // 如果当前节点h的左子节点不为null，将左子节点放入队列queue中，同时将尾部索引r加1
            if (h.left!= null) {
                queue[r++] = h.left;
            }
            // 如果当前节点h的右子节点不为null，将右子节点放入队列queue中，同时将尾部索引r加1
            if (h.right!= null) {
                queue[r++] = h.right;
            }
            // 如果当前节点h的左子节点为null或者右子节点为null，说明已经遇到了孩子节点不双全的节点，将leaf标志设置为true
            if (h.left == null || h.right == null) {
                leaf = true;
            }
        }
        // 如果层次遍历完成（while循环结束），没有触发返回false的条件，说明该二叉树满足完全二叉树的条件，返回true
        return true;
    }
}